package com.example.demo.his.leetcode;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @auther zzc
 * @date 2021/4/8 10:31
 */
public class 两个数组的交集 {

    //1、用哈希表
    //给定两个数字数组  找出交集数字集合
    //思路：记录每个数字出现的次数  取两边出现次数最小的数字集合
    public int[] intersectNums(int[] nums1, int[] nums2) {
        //先遍历较短的数组
        if (nums1.length > nums2.length) {
            return intersectNums(nums2, nums1);
        }
        //记录num1集合中每个数字出现的次数
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums1) {

            //如果map中不存在num 则count=1,如果map中存在num,则count=count+1
            int count = map.getOrDefault(num, 0) + 1;
            map.put(num, count);
        }
        //交集集合
        int[] intersect = new int[nums1.length];
        int index = 0;
        for (int num : nums2) {
            //查num在num1中出现的次数
            int count = map.getOrDefault(num, 0);
            //如果存在，则加进交集集合 intersect
            if (count > 0) {
                intersect[index++] = num;
            }
            count--;
            if (count > 0) {
                map.put(num, count);
            } else {
                map.remove(num);
            }
        }
        return Arrays.copyOfRange(intersect, 0, index);
    }

    //2、双指针+栈
    //先排序  双指针比较两个num
    public int[] intersectNum2(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int intersect[] = new int[nums1.length];
        int index1 = 0;
        int index2 = 0;
        int index = 0;
        while (index1 < nums1.length && index2 < nums2.length) {
            if (nums1[index1] < nums2[index2]) {
                index1++;
            } else if (nums1[index1] > nums2[index2]) {
                index2++;
            } else {
                intersect[index++] = nums1[index1++];
                index2++;
            }
        }
        return Arrays.copyOfRange(intersect, 0, index);
    }
}
